package 动态规划.四键键盘;

public class 四键键盘_651 {
    public static void main(String[] args) {
        System.out.println(new 四键键盘_651().maxA(3));
    }

    public int maxA(int N) {
        //dp[N] 代表N次按键后A的数量
        int dp[] = new int[N + 1];//长度为N+1是为了填入base case dp[0]=0
        //base case
        dp[0] = 0;

        for (int i = 1; i <= N; i++) {
            //此次按的是A键,那么产生的A就是上次的A数量加1
            dp[i] = dp[i - 1] + 1;
            /*用j来保存上一次按完C-A,C-C的时机，此时剪贴板中A的个数就是dp[j-2]
            因为  比如按键顺序如下A,A,A,C-A,C-C。j=5，但是A的数量为dp[j-2]=dp[3]。

            下面j从2开始也是同理。因为要有dp[j-2]所以j必须大于等于2才会让j-2始终大于等于0
            也可以理解为就是第一次按键就是C-A,C-C那也要两次按键。
             */
            for (int j = 2; j < i; j++) {
                //选出按A键，和按C-A,C-C后再按C-V键那个A数量多。
                dp[i] = Math.max(dp[i], dp[j - 2] * (i - j + 1));
            }
        }

        return dp[N];
    }
}
